// @algorithm @lc id=212 lang=cpp 
// @title word-search-ii


#define print(...)
// @test([["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],["oath","pea","eat","rain"])=["eat","oath"]
// @test([["a","b"],["c","d"]],["abcb"])=[]
// @test([["o","a","b","n"],["o","t","a","e"],["a","h","k","r"],["a","f","l","v"]], ["oa","oaa"])=["oa","oaa"]
class Solution {
    struct Trie{
        bool used;
        string word;
        vector<shared_ptr<Trie>> children;
        Trie(string w=""):used(false),word(w),children(26, nullptr){}
    };
    shared_ptr<Trie> dict = make_shared<Trie>();
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        print("\n", words, "\n")
        print(Mat(board))
        for(auto & w : words){
            auto node = dict;
            for(auto &c : w){
                auto it = node->children.begin() + c - 'a';
                if(!*it) *it = make_shared<Trie>();
                node = *it;
            }
            node->word = w;
        }

        pair<int,int> dir[] = { {0,1}, {0,-1}, {1,0}, {-1,0} };
        int m = board.size(), n = board[0].size();
        vector<string> ans;
        function<void(int,int,shared_ptr<Trie>)> dfs =
        [&](int i, int j, shared_ptr<Trie> node){
            if(!node) return;
            if(node->word.size() && !node->used){
                ans.push_back(node->word);
                node->used = true;
            }
            auto ch = board[i][j];
            board[i][j] = '#';
            for(auto &[di, dj] : dir){
                if(i+di<0||m<=i+di || j+dj<0||n<=j+dj) continue;
                if('#' == board[i+di][j+dj]) continue;
                dfs(i+di, j+dj, node->children[board[i+di][j+dj]-'a']);
            }
            board[i][j] = ch;
        };
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                dfs(i, j, dict->children[board[i][j]-'a']);
        return ans;
    }
};